package com.lfg.leetcode.leetcode0;


import com.alibaba.fastjson.JSONArray;

import java.util.*;

public class No56merge {

    public static void main(String[] args) {
        List<Interval> list = new ArrayList<>();

        list.add(new Interval(4, 6));
//        list.add(new Interval(3, 5));
//        list.add(new Interval(1, 2));
//        list.add(new Interval(8, 9));


        list = merge(list);
        System.out.println(JSONArray.toJSONString(list));
    }

    public static List<Interval> merge(List<Interval> intervals) {
        List<Interval> ret = new ArrayList<>();

        if (intervals == null || intervals.size() <= 1) {
            return intervals;
        }
        int size = intervals.size();
        int[] start = new int[size];
        int[] end = new int[size];
        for (int i = 0; i < size; i++) {
            Interval interval = intervals.get(i);
            start[i] = interval.start;
            end[i] = interval.end;
        }

        Arrays.sort(start);
        Arrays.sort(end);
        int startIndex = 0;
        for (int i = 1; i < size; i++) {
            if (start[i] > end[i - 1]) {
                ret.add(new Interval(start[startIndex], end[i - 1]));
                startIndex = i;
            }
        }
        if (startIndex != size) {
            ret.add(new Interval(start[startIndex], end[size - 1]));
        }
        return ret;
    }

    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] == o2[0]? o1[1]-o2[1]: o1[0]-o2[0];
            }
        }
        );
        List<Interval> ret = new ArrayList<>(intervals.length);
        Interval last = null;
        for (int i = 0; i < intervals.length; i++) {
            if (last == null) {
                last = new Interval(intervals[i][0], intervals[i][1]);
                ret.add(last);
            } else if (last.end >= intervals[i][0]) {
                if(last.end<intervals[i][1]) {
                    last.end = intervals[i][1];
                }
            } else {
                last = new Interval(intervals[i][0], intervals[i][1]);
                ret.add(last);
            }
        }
        int[][] data = new int[ret.size()][2];
        int index =0;
        for(Interval record : ret){
            data[index][0] = record.start;
            data[index][1] = record.end;
            index++;
        }
        return data;
    }
}


class Interval {

    int start;
    int end;

    Interval(int s, int e) {
        start = s;
        end = e;
    }

    public int getStart() {
        return start;
    }

    public void setStart(int start) {
        this.start = start;
    }

    public int getEnd() {
        return end;
    }

    public void setEnd(int end) {
        this.end = end;
    }
}

